package likou.tanxin;

/**
 * @author: Tangxz
 * @email:1171702529@qq.com
 * @cate: 2020/11/02 09:06
 */
public class _757 {
    public static void main(String[] args) {

    }

    public int intersectionSizeTwo(int[][] intervals) {
        int count = 0;
        int n1, n2;
        //快排
        quickSort(intervals, 0, intervals.length - 1);
        n1 = intervals[intervals.length - 1][0];
        n2 = intervals[intervals.length - 1][0] + 1;
        count = 2;
        for (int i = intervals.length - 2; i >= 0; i--) {
            int j = count(intervals[i], n1, n2);
            if (j == 0) {
                n1 = intervals[i][0];
                n2 = intervals[i][0] + 1;
                count += 2;
            } else if (j == 1) {
                n2 = n1;
                n1 = intervals[i][0];
                count++;
            }
        }
        return count;
    }

    public int count(int[] interval, int n1, int n2) {
        int count = 0;
        if (interval[0] <= n1 && interval[interval.length - 1] >= n1) {
            count++;
        }
        if (interval[0] <= n2 && interval[interval.length - 1] >= n2) {
            count++;
        }
        return count;
    }

    public void quickSort(int[][] intervals, int start, int end) {
        if (start >= end) {
            return;
        }
        int p = partition(intervals, start, end);
        quickSort(intervals, start, p - 1);
        quickSort(intervals, p + 1, end);
    }

    public int partition(int[][] intervals, int start, int end) {
        int p = start, q = start;
        //根据最后一个元素进行快排
        int[] temp = intervals[end];
        //左侧开始单向遍历intervals数组
        //p永远指向比temp[0]小的当前元素的下一个位置。
        while (q < end) {
            if (intervals[q][0] < temp[0]) {
                int[] temp2 = intervals[p];
                intervals[p] = intervals[q];
                intervals[q] = temp2;
                p++;
            } else if (intervals[q][0] == temp[0] && intervals[q][1] > temp[1]) {
                int[] temp2 = intervals[p];
                intervals[p] = intervals[q];
                intervals[q] = temp2;
                p++;
            }
            q++;
        }
        int[] temp2 = intervals[p];
        intervals[p] = intervals[end];
        intervals[end] = temp2;
        return p;
    }

    public void quick(int[] ints,int start,int end){
        if (start>end){
            return;
        }
        int p = part(ints,start,end);
        quick(ints,p+1,end);
        quick(ints,start,p-1);
    }

    private int part(int[] ints, int start, int end) {
        int p = start,q=start;
        int temp = ints[end];
        while (p<end){
            if (ints[p]<temp){
                int temp2 = ints[q];
                ints[q] = ints[p];
                ints[p] = temp2;
                q++;
            }
            p++;
        }
        int temp2 = ints[q];
        ints[p] = ints[q];
        ints[q] = temp2;
        return q;
    }

}
